//
//  linkedList.h
//  labuladong
//
//  Created by 刘振舟 on 2023/5/16.
//

#ifndef linkedList_h
#define linkedList_h

#include <vector>
#include <queue>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class LinkedListSolution {
    
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2);
    
    ListNode* partition(ListNode* head, int x);

    ListNode* mergeKLists(vector<ListNode*>& lists);

    ListNode* removeNthFromEnd(ListNode* head, int n);

    ListNode* middleNode(ListNode* head);

    ListNode* detectCycle(ListNode* head);
    
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB);
    
    ListNode* deleteDuplicates(ListNode *head);
    
    ListNode* reverseList(ListNode* head);
    
    ListNode* reverseBetween(ListNode* head, int left, int right);
    
    ListNode* reverseKGroup(ListNode* head, int k);
    
    ListNode *left = nullptr;
    
    bool traverseLinkedList(ListNode* right) {
        if (right == nullptr) {
            return true;
        }
        bool res = traverseLinkedList(right->next);
        res = res & (left->val == right->val ? true : false);
        left = left->next;
        return res;
    }
    
    bool isPalindrome(ListNode* head) {
        left = head;
        return traverseLinkedList(head);
    }
    
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr || k == 0 || head->next == nullptr) {
            return head;
        }
        
        ListNode* iter = head;
        int n = 1;
        while (iter->next) {
            ++n;
            iter = iter->next;
        }
        
        int rest = n - k % n;
        if (rest == n) {
            return head;
        }
        iter->next = head;
        while (rest--) {
            iter = iter->next;
        }
        ListNode* res = iter->next;
        iter->next = nullptr;
        return res;
    }
};

#endif /* linkedList_h */
